﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LK.Math
{
    public partial class Bits
    {
		/// <summary>
		/// 按位指定两个数组中的相同比特数的记录进行大小大小
		/// </summary>
		/// <param name="arr1">数组1</param>
		/// <param name="startBitPosition1">数组1的起始位索引</param>
		/// <param name="arr2">数组2</param>
		/// <param name="startBitPosition2">数组2的起始位索引</param>
		/// <param name="bitsCount">比较的比特数量</param>
		/// <returns>前者大返回1，相等返回0，后者大返回-1</returns>
		static public int Compare(ulong[] arr1, int startBitPosition1, ulong[] arr2, int startBitPosition2, int bitsCount) {
			if (bitsCount == 0) return 0;
			int p1 = 0;
			int p2 = 0;
			if (startBitPosition1 < 0) { p1 += (startBitPosition1 - 63) / 64; startBitPosition1 &= 63; }
			else if (startBitPosition1 >= 64) { p1 += startBitPosition1 / 64; startBitPosition1 &= 63; }
			if (startBitPosition2 < 0) { p2 += (startBitPosition2 - 63) / 64; startBitPosition2 &= 63; }
			else if (startBitPosition2 >= 64) { p2 += startBitPosition2 / 64; startBitPosition2 &= 63; }

			int bmv1 = bitsCount + startBitPosition1;
			int bmv2 = bitsCount + startBitPosition2;
			ulong num1, num2;
			if (bitsCount <= 64)
			{
				num1 = arr1[p1] >> startBitPosition1;
				num2 = arr2[p2] >> startBitPosition2;
				if (startBitPosition1 + bitsCount > 64) num1 |= arr1[p1+1] << ((64) - startBitPosition1);
				if (startBitPosition2 + bitsCount > 64) num2 |= arr2[p2+1] << ((64) - startBitPosition2);
				if (bitsCount != (64))
				{
					num1 &= (~0ul) >> ((64) - bitsCount);
					num2 &= (~0ul) >> ((64) - bitsCount);
				}
				return num1 > num2 ? 1 : num1 < num2 ? -1 : 0;
			}

			int bc1 = bmv1 & (63);
			int bc2 = bmv2 & (63);

			bmv1 /= 64;
			bmv2 /= 64;

			int sp1 = p1 + bmv1;
			int sp2 =p2 + bmv2;

			if (bc1 != 0)
			{
				num1 = arr1[sp1] << ((64) - bc1);
				num2 = bc2 == 0 ? 0 : arr2[sp2] << ((64) - bc2);
				if (bc1 >= bc2) num2 |= arr2[sp2 - 1] >> bc2;
				num2 &= (~0ul) << ((64) - bc1);
				if (num1 != num2) return num1 > num2 ? 1 : -1;
			}
			if (sp1 != p1)
			{
				if (bc1 > bc2)
				{
					int bc = bc1 - bc2;
					while (--sp1 != p1)
					{
						--sp2;
						num1 = arr1[sp1];
						num2 = (arr2[sp2] << bc) | (arr2[sp2 - 1] >> ((64) - bc));
						if (num1 != num2) return num1 > num2 ? 1 : -1;
					}
				}
				else if (bc1 == bc2)
				{
					while (--sp1 != p1)
					{
						 num1 = arr1[sp1];
						 num2 = arr2[--sp2];
						if (num1 != num2) return num1 > num2 ? 1 : -1;
					}
				}
				else
				{
					int bc = bc2 - bc1;
					while (--sp1 != p1)
					{
						num1 = arr1[sp1];
						num2 = (arr2[sp2] << ((64) - bc)) | (arr2[sp2 - 1] >> bc);
						if (num1 != num2) return num1 > num2 ? 1 : -1;
						--sp2;
					}
				}
			}
			num1 = arr1[p1] >> startBitPosition1;
			num2 = arr2[p2] >> startBitPosition2;
			if (startBitPosition2 != 0 && (startBitPosition1 == 0 || startBitPosition1 < startBitPosition2)) num2 |= arr2[p2+1] << ((64) - startBitPosition2);
			num2 &= (~0ul) >> startBitPosition1;
			return num1 > num2 ? 1 : num1 < num2 ? -1 : 0;
		}

		/// <summary>
		/// 按最高位对齐的方式比较两个数组，数组长度可以不等
		/// </summary>
		/// <param name="arr1">数组1</param>
		/// <param name="arr2">数组2</param>
		/// <returns>前者大返回1，后者大返回-1，相等返回0</returns>
		/// <remarks>当两者长度不相等时，如果较长者长出部分全为0，则判定2者相等</remarks>
		static public int HighAlignCompare(ulong[] arr1, ulong[] arr2) { return HighAlignCompare(arr1, arr1.Length, arr2, arr2.Length); }
		static public int HighAlignCompare(ulong[] arr1,int arrLength1, ulong[] arr2, int arrLength2) {
			while (arrLength1 != 0 && arrLength2 != 0)
			{
				--arrLength1; --arrLength2;
				if (arr1[arrLength1] != arr2[arrLength2]) return arr1[arrLength1] > arr2[arrLength2] ? 1 : -1;
			}
			if (arrLength1 == 0) { for (int i = 0; i < arrLength2; ++i) if (arr2[i] != 0) return -1; return 0; }
			for (int i = 0; i < arrLength1; ++i) if (arr1[i] != 0) return 1;
			return 0;
		}
		/// <summary>
		/// 以高位对齐的方式比较两组数据，获取两者相差数值最高位的1与arr1所指定比特最高位的距离。两者比特数可以不等。比如10000和01111比较将返回5
		/// </summary>
		/// <param name="arr1">数组1</param>
		/// <param name="startBitPosition1">指定数组1中起始位索引</param>
		/// <param name="bitCount1">指定数组1中需比较的比特数</param>
		/// <param name="arr2">数组2</param>
		/// <param name="startBitPosition2">指定数组2中起始位索引</param>
		/// <param name="bitCount2">指定数组2中需比较的比特数</param>
		/// <param name="mov">arr2高位相对arr1偏移，大于0为向左偏移，小于0为向右。向左偏移超出arr1中指定的最高位部分将被忽略</param>
		/// <returns>当前者较大时为正值，当后者较大时为负值，相等为0。绝对值表示差值1所在最高位与前者所制定范围的最高位的偏移量，与arr1所指定范围最高位相等时为1</returns>
		static public int HighAlignDifferenceBitIndex(ulong[] arr1, int startBitPosition1, int bitCount1, ulong[] arr2, int startBitPosition2, int bitCount2, int mov) {
			int p1=0, p2=0;
			if (startBitPosition1 < 0) { p1 += (startBitPosition1 - 63) / 64; startBitPosition1 &=63; }
			else if (startBitPosition1 >= 64 ){ p1 += startBitPosition1 / 64; startBitPosition1 &= 63; }
			if (startBitPosition2 < 0) { p2 += (startBitPosition2 - 63) / 64; startBitPosition2 &= 63; }
			else if (startBitPosition2 >= 64 ){ p2 += startBitPosition2 / 64; startBitPosition2 &= 63; }


			int abc1 = startBitPosition1 + bitCount1;
			int abc2 = startBitPosition2 + bitCount2;

			int ps1 = p1+ (abc1 == 0 ? 0 : (abc1 - 1) / 64);//指针
			int ps2 = p2 + (abc2 == 0 ? 0 : (abc2 - 1) / 64);

			int tbc1 = 0;//已读取比特数
			int tbc2 = 0;
			int state = 0;

			abc1 &= 63;//高位比特偏移
			abc2 &= 63;

			for (; ; )
			{
				ulong num1;
				if (tbc1 >= bitCount1) { if (tbc2 >= bitCount2) break; num1 = 0; }
				else
				{
					if (mov >= 64) { num1 = 0; }
					else
					{
						if (mov <= 0)
							num1 = abc1 == 0 ?arr1[ps1]: ((arr1[ps1] << (64- abc1)) | (ps1<=0?0:(arr1[ps1-1] >> abc1)));
						else
						{
							if (abc1 == 0)
								num1 = tbc1 == 0 ? ps1<0?0:(arr1[ps1] >> mov) : (arr1[ps1+1]<< (64- mov)) | (ps1<0?0:(arr1[ps1] >> mov));
							else
							{
								if (tbc1 == 0)
									num1 = ((arr1[ps1] << (64- abc1)) | (ps1<=0?0:(arr1[ps1-1] >> abc1))) >> mov;
								else
								{
									if (mov + abc1 > 64) num1 = (arr1[ps1+1]<< (8 * 16 - (abc1 + mov))) | (ps1<0?0:(arr1[ps1] >> (mov + abc1 - (64))));
									else if (mov + abc1 == 64) num1 = arr1[ps1];
									else num1 = (arr1[ps1] << ((64 - mov - abc1)) | (ps1<=0?0:(arr1[ps1-1] >> (abc1 + mov))));
								}
							}
						}
						if (tbc1 == 0 && mov > 0)
						{
							if (tbc1 + 64- mov > bitCount1)
								num1 &= (~0ul) << (tbc1 - mov - bitCount1 + 64);
						}
						else if (tbc1 + 64> bitCount1)
							num1 &= (~0ul) << (tbc1 - bitCount1 + 64);
						--ps1;
					}
				}
				ulong num2;
				if (tbc2 >= bitCount2) { num2 = 0; }
				else
				{
					if (mov <= -64) { num2 = 0; }
					else
					{
						if (mov >= 0)
							num2 = abc2 == 0 ? arr2[ps2] : ((arr2[ps2] << (64- abc2)) | (ps2<=0?0:(arr2[ps2-1] >> abc2)));
						else
						{
							if (abc2 == 0)
								num2 = tbc2 == 0 ? (arr2[ps2] >> -mov) : (arr2[ps2+1] << (64+ mov)) | (ps2<0?0:(arr2[ps2] >> -mov));
							else
							{
								if (tbc2 == 0)
									num2 = ((arr2[ps2] << (64- abc2)) | (ps2<=0?0:(arr2[ps2-1] >> abc2))) >> -mov;
								else
								{
									if (abc2 - mov > 64 )num2 = (arr2[ps2+1] << (8 * 16 - (abc2 - mov))) | (ps2<0?0:(arr2[ps2] >> (abc2 - mov - (64))));
									else if (abc2 - mov == 64 )num2 = arr2[ps2];
									else num2 = (arr2[ps2] << ((64 + mov - abc2)) | (ps2<=0?0:(arr2[ps2-1] >> (abc2 - mov))));
								}
							}
						}
						if (tbc2 == 0 && mov < 0)
						{
							if (tbc2 + 64+ mov > bitCount2)
								num2 &= (~0ul) << (tbc2 + mov - bitCount2 + 64);
						}
						else if (tbc2 + 64> bitCount2)
							num2 &= (~0ul) << (tbc2 - bitCount2 + 64);
						--ps2;
					}
				}
				if (state == 0)
				{
					if (num1 != num2)
					{
						if (num1 > num2)
						{
							if (num1 != num2 + 1)
								return (tbc1 > tbc2 ? tbc1 : tbc2) +  LeftZeroCount64(num1 - num2) + 1;
							state = 1;
						}
						else
						{
							if (num2 != num1 + 1)
								return -(tbc1 > tbc2 ? tbc1 : tbc2) -  LeftZeroCount64(num2 - num1) - 1;
							state = -1;
						}
					}
				}
				else if (state == 1)
				{
					if (num1 != 0 || num2 != ~0ul)
					{
						if (tbc1 < tbc2) tbc1 = tbc2;
						if (num1 < num2) return tbc1 +  LeftZeroCount64(num1 - num2) + 1;
						return tbc1;
					}
				}
				else if (num2 != 0 || num1 != ~0ul)
				{
					if (tbc1 > tbc2) tbc2 = tbc1;
					if (num2 < num1) return -tbc2 - LeftZeroCount64(num2 - num1) - 1;
					return -tbc2;
				}

				if (mov >= 64)
				{
					mov -=64;
					tbc2 += 64;
				}
				else if (mov <= -64)
				{
					mov += 64;
					tbc1 += 64;
				}
				else
				{
					if (mov > 0)
					{
						if (tbc1 == 0) tbc1 = -mov;
					}
					else if (mov < 0)
					{
						if (tbc2 == 0) tbc2 = mov;
					}
					tbc1 += 64;
					tbc2 += 64;
				}
			}
			if (state == 0)
				return 0;
			if (state == 1) return (tbc1 > tbc2 ? tbc1 : tbc2);
			return -(tbc1 > tbc2 ? tbc1 : tbc2);
		}
	}
}
